#include <vector>

using std::vector;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> v = vector<int>(triangle.size() * 2);
        v[0] = triangle[0][0];
        v[1] = v[0];
        int i = 1;
        while (i < triangle.size()) {
            v[0] += triangle[i][0];
            for (int j = 1; j < i; j++) {
                v[j * 2] = std::min(v[j * 2 - 1], v[2 * j]) + triangle[i][j];
            }
            v[2 * i] = v[2 * i - 1] + triangle[i][i];
            for (int j = 0; j <= i; j++) {
                v[2 * j + 1] = v[2 * j];
            }
            i++;
        }
        int min = v[0];
        for (i = 1; i < v.size(); i += 2) {
            if (v[i] < min) {
                min = v[i];
            }
        }
        return min;
    }
};